#pragma once

#include <iostream>
#include <vector>
using namespace std;

template <class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template <>
struct HashFunc<string>
{
	size_t operator()(const string& str)
	{
		size_t hashi = 0;

		for (auto ch : str)
		{
			hashi += ch;
			hashi *= 31;
		}

		return hashi;
	}
};

namespace OpenAdress
{
	enum State
	{
		EXIT,
		EMPTY,
		DELETE
	};

	template <class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template <class K, class V>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		/*bool insert(const pair<K, V>& kv)
		{
			if (find(kv.first))
			{
				return false;
			}

			if (_n * 10 / _tables.size() == 7)
			{
				vector<HashData<K,V>> newtables(2 * _tables.size());

				for (auto data : _tables)
				{
					if (data._state == EXIT)
					{
						size_t hashi = data._kv.first % newtables.size();

						size_t i = 1;
						size_t index = hashi;

						while (newtables[index]._state == EXIT)
						{
							index = hashi + i;
							i++;

							index %= newtables.size();
						}

						newtables[index]._kv = kv;
						newtables[index]._state = EXIT;
					}
				}

				newtables.swap(_tables);
			}

			size_t hashi = kv.first % _tables.size();

			size_t i = 1;
			size_t index = hashi;

			while (_tables[index]._state == EXIT)
			{
				index = hashi + i;
				i++;

				index %= _tables.size();
			}

			_tables[index]._kv = kv;
			_tables[index]._state = EXIT;
			++_n;
			return true;
		}*/

		void FindIndex(size_t hashi, vector<HashData<K, V>>& _tables, const pair<K, V>& kv)
		{


			size_t i = 1;
			size_t index = hashi;

			while (_tables[index]._state == EXIT)
			{
				index = hashi + i;
				i++;

				index %= _tables.size();
			}

			_tables[index]._kv = kv;
			_tables[index]._state = EXIT;
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (find(kv.first))
			{
				return false;
			}

			if (_n * 10 / _tables.size() == 7)
			{
				vector<HashData<K, V>> newtables(2 * _tables.size());

				for (auto data : _tables)
				{
					if (data._state == EXIT)
					{
						size_t hashi = data._kv.first % newtables.size();

						FindIndex(hashi, newtables, data._kv);
					}
				}

				newtables.swap(_tables);
			}

			size_t hashi = kv.first % _tables.size();
			FindIndex(hashi, _tables, kv);

			++_n;
			return true;
		}

		bool insert(const pair<K, V>& kv)
		{
			if (find(kv.first))
			{
				return false;
			}

			if (_n * 10 / _tables.size() == 7)
			{
				HashTable<K, V> newht;
				newht._tables.resize(2 * _tables.size());

				for (auto data : _tables)
				{
					if (data._state == EXIT)
					{
						newht.insert(data._kv);
					}
				}

				newht._tables.swap(_tables);
			}

			size_t hashi = kv.first % _tables.size();

			size_t i = 1;
			size_t index = hashi;

			while (_tables[index]._state == EXIT)
			{
				index = hashi + i;
				i++;

				index %= _tables.size();
			}

			_tables[index]._kv = kv;
			_tables[index]._state = EXIT;
			++_n;
			return true;
		}

		HashData<K, V>* find(const K& key)
		{
			size_t hashi = key % _tables.size();
			size_t i = 1;
			size_t index = hashi;

			while (_tables[index]._state != EMPTY)
			{
				if (_tables[index]._state == EXIT && _tables[index]._kv.first == key)
				{
					return &_tables[index];
				}

				index = hashi + i;
				i++;

				if (index == hashi)
				{
					return nullptr;
				}
			}

			return nullptr;
		}

		bool erase(const K& key)
		{
			HashData<K, V>* ret = find(key);

			if (ret != nullptr)
			{
				return false;
			}
			else
			{
				ret->state = DELETE;
				_n--;
				return true;
			}

		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;
	};

}

namespace HashBbcket
{
	template<class K,class V>
	struct HashData
	{
		pair<K, V> _kv;
		HashData<K, V>* _next;

		HashData(const pair<K,V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};

	template<class K,class V>
	class HashTable
	{
		typedef HashData<K, V> Node;
	public:
		~HashTable()
		{
			for (auto& data : _tables)
			{
				Node* cur = data;

				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}

				data = nullptr;
			}
		}

		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		bool insert(const pair<K, V>& kv)
		{
			if (find(kv.first))
			{
				return false;
			}

			if (_n == _tables.size())
			{
				vector<Node*> newtables(2 * _tables.size());

				for (auto& data : _tables)
				{
					size_t hashi = data->_kv.first % newtables.size();
					Node* cur = data;

					while (cur)
					{
						Node* next = cur->_next;
						/*cur->_next = newtables[hashi];
						newtables[hashi]->_next = cur;*/

						Node* pcur = cur;
						Node* prev = nullptr;

						if (newtables[hashi] == nullptr)
						{
							newtables[hashi] = cur;
						}
						else
						{
							while (pcur)
							{
								prev = pcur;
								pcur = pcur->_next;
							}

							prev->_next = cur;
						}

						cur = next;
					}

					data = nullptr;
				}
			}

			size_t hashi = kv.first % _tables.size();

			Node* newnode = new Node(kv);

			/*newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;*/

			Node* prev = nullptr;
			Node* cur = _tables[hashi];

			if (_tables[hashi] == nullptr)
			{
				_tables[hashi] = newnode;
			}
			else
			{
				while (cur)
				{
					prev = cur;
					cur = cur->_next;
				}

				prev->_next = newnode;
			}


			++_n;
			return true;
		}

		Node* find(const K& key)
		{
			size_t hashi = key % _tables.size();
			Node* cur = _tables[hashi];

			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}

				cur = cur->_next;
			}

			return nullptr;
		}

		bool erase(const K& key)
		{
			size_t hashi = key % _tables.size();

			Node* prev = nullptr;
			Node* cur = _tables[hashi];

			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
}